package org.example.myleet.topologicalsort;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.Parser;

import java.util.*;

public class TopologicalSortSolution {

    /**
     * 207【拓扑排序+BFS】课程表
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inputDegrees = new int[numCourses];
        List<Integer>[] map = new ArrayList[numCourses];
        for (int[] prerequisite : prerequisites) {
            inputDegrees[prerequisite[0]]++;
            List<Integer> nextNodes = null != map[prerequisite[1]] ? map[prerequisite[1]] : new ArrayList<>();
            nextNodes.add(prerequisite[0]);
            map[prerequisite[1]] = nextNodes;
        }
        int visitedCnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (inputDegrees[i] < 1) {
                queue.offer(i);
                visitedCnt++;
            }
        }
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                int course = queue.poll();
                List<Integer> nextCourses = map[course];
                if (null != nextCourses && nextCourses.size() > 0) {
                    for (int nextCourse : nextCourses) {
                        inputDegrees[nextCourse]--;
                        if (inputDegrees[nextCourse] < 1) {
                            queue.offer(nextCourse);
                            visitedCnt++;
                        }
                    }
                }
            }
        }
        return visitedCnt == numCourses;
    }

    /**
     * 210【拓扑排序+BFS】课程表 II
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] degrees = new int[numCourses];
        Map<Integer, List<Integer>> nextMap = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            degrees[prerequisite[0]]++;
            List<Integer> next = nextMap.getOrDefault(prerequisite[1], new LinkedList<>());
            next.add(prerequisite[0]);
            nextMap.put(prerequisite[1], next);
        }
        int[] answer = new int[numCourses];
        int i = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int j = 0; j < numCourses; ++j) {
            if (degrees[j] < 1) {
                queue.offer(j);
                answer[i++] = j;
            }
        }
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int j = 0; j < n; ++j) {
                int course = queue.poll();
                List<Integer> next = nextMap.get(course);
                if (null != next) {
                    for (int nextCourse : next) {
                        degrees[nextCourse]--;
                        if (degrees[nextCourse] < 1) {
                            queue.offer(nextCourse);
                            answer[i++] = nextCourse;
                        }
                    }
                }
            }
        }
        if (i == numCourses) {
            return answer;
        }
        return new int[0];
    }

    /**
     * 310【拓扑排序】最小高度树
     */
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        //重新构建图
        Map<Integer, Set<Integer>> graph = new HashMap<>(n);
        for (int[] edge : edges) {
            Set<Integer> edgeList = graph.computeIfAbsent(edge[0], key -> new HashSet<>());
            edgeList.add(edge[1]);
            graph.put(edge[0], edgeList);
            edgeList = graph.computeIfAbsent(edge[1], key -> new HashSet<>());
            edgeList.add(edge[0]);
            graph.put(edge[1], edgeList);
        }
        //BFS队列存储最外圈的节点
        Queue<Integer> queue = new LinkedList<>();
        for (Integer node : graph.keySet()) {
            if (graph.get(node).size() == 1) {
                queue.offer(node);
            }
        }
        //记录每个节点的层级
        int[] levels = new int[n];
        int size, level = 0, maxLevel = 0;
        //下面通过BFS的方式找到图中的最小高度树的根节点，原理是拓扑排序
        while (!queue.isEmpty()) {
            size = queue.size();
            for (int i = 0; i < size; ++i) {
                //记录当前层级的节点的层级
                int node = queue.poll();
                levels[node] = level;
                maxLevel = level;
                Set<Integer> neighbours = graph.get(node);
                for (int neighbour : neighbours) {
                    //找到当前节点的相邻节点，移除其边
                    Set<Integer> neighbourLinks = graph.get(neighbour);
                    neighbourLinks.remove(node);
                    if (neighbourLinks.size() == 1) {
                        //若相邻节点降了度到1，则相邻节点入队
                        queue.offer(neighbour);
                    }
                }
                //移除当前节点
                graph.remove(node);
            }
            ++level;
        }
        List<Integer> candidates = new ArrayList<>(2);
        for (int i = 0; i < n; ++i) {
            if (levels[i] == maxLevel) {
                //找到所有最高层级的点，即为高度最小的树的根
                candidates.add(i);
            }
        }
        return candidates;
    }

    //p2050
    public int minimumTime(int n, int[][] relations, int[] time) {
        //重建图，记录每个节点n的前驱结点和后续结点
        int[] prevNodeCounts = new int[n + 1];
        Set<Integer>[] prevNodeSets = new HashSet[n + 1];
        Set<Integer>[] nextNodeSets = new HashSet[n + 1];
        for (int[] relation : relations) {
            int prev = relation[0];
            int next = relation[1];
            //记录节点n的前驱结点
            if (prevNodeSets[next] == null) {
                prevNodeSets[next] = new HashSet<>();
            }
            prevNodeSets[next].add(prev);
            ++prevNodeCounts[next];
            //记录节点n的后续结点
            if (nextNodeSets[prev] == null) {
                nextNodeSets[prev] = new HashSet<>();
            }
            nextNodeSets[prev].add(next);
        }
        int answer = 0;
        int[] nodesEarliestEndTime = new int[n + 1];
        //存储拓扑排序中入度为0的结点，作为下一步被访问的结点
        Queue<Integer> queue = new LinkedList<>();
        //先找到第一批入度为0的结点
        for (int i = 1; i <= n; ++i) {
            if (prevNodeCounts[i] == 0) {
                queue.offer(i);
                nodesEarliestEndTime[i] = time[i - 1];
                answer = Math.max(answer, time[i - 1]);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> nextNodes = new ArrayList<>();
            for (int i = 0; i < size; ++i) {
                int node = queue.poll();
                Set<Integer> nextNodeSet = nextNodeSets[node];
                if (null != nextNodeSet) {
                    for (int next : nextNodeSet) {
                        --prevNodeCounts[next];
                        if (prevNodeCounts[next] <= 0) {
                            queue.offer(next);
                            nextNodes.add(next);
                        }
                    }
                    for (int next : nextNodes) {
                        int maxPrevEnd = 0;
                        Set<Integer> prevNodeSet = prevNodeSets[next];
                        for (int prevNode : prevNodeSet) {
                            maxPrevEnd = Math.max(maxPrevEnd, nodesEarliestEndTime[prevNode]);
                        }
                        nodesEarliestEndTime[next] = maxPrevEnd + time[next - 1];
                        answer = Math.max(answer, nodesEarliestEndTime[next]);
                    }
                }
            }
        }
        return answer;
    }

    /**
     * 2127【分类讨论+拓扑排序】参加会议的最多员工数
     */
    public int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        //记录每个结点的父结点集合，复制一份，因为后面需要一份修改，一份保持原装用于溯源
        Set<Integer>[] prev = new Set[n];
        Set<Integer>[] prev1 = new Set[n];
        for (int i = 0; i < n; ++i) {
            int f = favorite[i];
            if (null == prev[f]) {
                prev[f] = new HashSet<>();
                prev1[f] = new HashSet<>();
            }
            prev[f].add(i);
            prev1[f].add(i);
        }
        //移除所有不成环的结点（没有入度），用BFS（拓扑排序）的方式不断地移除入度为空的不成环链式结点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (prev[i] == null) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int i = queue.poll();
            int f = favorite[i];
            if (null != prev[f]) {
                prev[f].remove(i);
                if (prev[f].isEmpty()) {
                    prev[f] = null;
                    queue.offer(f);
                }
            }
        }
        //下面分两类讨论，一类是环的结点数大于2的情况，这种环排他，只能整个环坐到桌子上，并且不能容纳其他环，所以第一类情况是取最大值
        //另一类是环的结点数等于2的情况，这种环不排他，能够容纳其他具有2个结点的环的其他链坐在一起，这种2结点环还能在两头都链接一条链
        //例如：3-4-5=6-7 和 1-2-9=10-11-12-13，这两个结构可以坐到一起，所以第二类情况是需要求和的
        int answer = 0;
        int circle2Sum = 0;
        for (int i = 0; i < n; ++i) {
            if (null == prev[i]) continue;
            int circleCnt = 1;
            //使用visited集合防止重复访问结点造成死循环
            Set<Integer> visited = new HashSet<>();
            visited.add(i);
            prev[i] = null;
            int next = favorite[i];
            while (!visited.contains(next)) {
                //跟着环链上结点逐个访问，获得环的长度
                visited.add(next);
                prev[next] = null;
                next = favorite[next];
                ++circleCnt;
            }
            if (circleCnt == 2) {
                //如果环的大小是2，则进入第二类情况的分类讨论
                //v保存已访问过的结点，防止死循环
                Set<Integer> v = new HashSet<>();
                v.add(next);
                v.add(favorite[next]);
                //用队列做BFS，这样可以得到链的最大长度，先从其中一个节点开始
                queue = new LinkedList<>();
                if (null != prev1[next]) {
                    for (int p : prev1[next]) {
                        if (!v.contains(p)) {
                            queue.offer(p);
                        }
                    }
                    prev1[next] = null;
                }
                while (!queue.isEmpty()) {
                    int s = queue.size();
                    for (int j = 0; j < s; ++j) {
                        int x = queue.poll();
                        if (null != prev1[x]) {
                            for (int p : prev1[x]) {
                                if (!v.contains(p)) {
                                    queue.offer(p);
                                }
                            }
                            prev1[x] = null;
                        }
                    }
                    //沿着链往外BFS，主键延长链+环的长度
                    ++circleCnt;
                }
                //再从另一个节点开始，也是做BFS找到最大的延长链长度
                if (null != prev1[favorite[next]]) {
                    for (int p : prev1[favorite[next]]) {
                        if (!v.contains(p)) {
                            queue.offer(p);
                        }
                    }
                    prev1[favorite[next]] = null;
                }
                while (!queue.isEmpty()) {
                    int s = queue.size();
                    for (int j = 0; j < s; ++j) {
                        int x = queue.poll();
                        if (null != prev1[x]) {
                            for (int p : prev1[x]) {
                                if (!v.contains(p)) {
                                    queue.offer(p);
                                }
                            }
                            prev1[x] = null;
                        }
                    }
                    ++circleCnt;
                }
                //第二类情况的每个组织是能够互相兼容的，所以可以加到一起
                circle2Sum += circleCnt;
            } else {
                //第一类情况不能每个组织互相兼容，只能取最大值
                answer = Math.max(answer, circleCnt);
            }
        }
        return Math.max(answer, circle2Sum);
    }

    /**
     * 2477【拓扑排序】到达首都的最少油耗
     */
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        Map<Integer, Set<Integer>> adjMat = new HashMap<>(n);
        for (int[] road : roads) {
            int a = road[0], b = road[1];
            Set<Integer> adjSet = adjMat.getOrDefault(a, new HashSet<>());
            adjSet.add(b);
            adjMat.put(a, adjSet);
            adjSet = adjMat.getOrDefault(b, new HashSet<>());
            adjSet.add(a);
            adjMat.put(b, adjSet);
        }
        if (adjMat.size() < 2) return 0;
        long answer = 0L;
        int[] nodeSubCnt = new int[n];
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < n; ++i) {
            if (adjMat.get(i).size() < 2) {
                //每个元素记录节点id及其子节点的大小
                q.offer(i);
                nodeSubCnt[i]++;
            }
        }
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int node = q.poll();
                answer += (nodeSubCnt[node] / seats) + (nodeSubCnt[node] % seats > 0 ? 1 : 0);
                Integer parent = null;
                Set<Integer> adjSet = adjMat.get(node);
                for (Integer p : adjSet) {
                    parent = p;
                    nodeSubCnt[parent] += nodeSubCnt[node];
                }
                if (null == parent) break;
                adjSet = adjMat.get(parent);
                adjSet.remove(node);
                if (0 != parent && adjSet.size() < 2) {
                    q.offer(parent);
                    nodeSubCnt[parent]++;
                }
            }
        }
        return answer;
    }

    /**
     * 2603【拓扑排序】收集树中金币
     * 思路：先将没有金币的叶子全部摘除，因为这些叶子是冗余的
     * 然后找出有金币的叶子结点，将这些结点删除后，如果其父结点只有1度，则一起删除，剩下的结点是必经的结点，数量v
     * 结果为max(0, (v-1)*2)
     */
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = coins.length;
        //将所有边转化为邻接矩阵，并记录边的度数
        Set<Integer>[] nodeNeighbours = new HashSet[n];
        int[] degrees = new int[n];
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            degrees[a]++;
            degrees[b]++;
            //写入a的邻接集合中
            Set<Integer> neighbours = nodeNeighbours[a];
            if (null == neighbours) neighbours = new HashSet<>();
            neighbours.add(b);
            nodeNeighbours[a] = neighbours;
            //写入b的邻接集合中
            neighbours = nodeNeighbours[b];
            if (null == neighbours) neighbours = new HashSet<>();
            neighbours.add(a);
            nodeNeighbours[b] = neighbours;
        }
        //queue放被移除的结点
        Queue<Integer> queue = new LinkedList<>();
        //将没有金币的叶子结点移除
        for (int i = 0; i < n; ++i) {
            if (degrees[i] == 1 && coins[i] < 1) {
                queue.offer(i);
                degrees[i] = 0;
            }
        }
        //拓扑排序，继续讲没有金币的叶子结点移除，直到找不到符合此条件的结点为止
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int x = queue.poll();
                Set<Integer> neighbours = nodeNeighbours[x];
                if (null != neighbours) {
                    for (int neighbour : neighbours) {
                        //x被移除，x的neighbour度数-1
                        degrees[neighbour]--;
                        if (degrees[neighbour] == 1 && coins[neighbour] < 1) {
                            //若neighbour也是没有金币的叶子结点，也进入移除的队列
                            queue.offer(neighbour);
                            degrees[neighbour] = 0;
                        }
                    }
                }
            }
        }
        //然后找出有金币的叶子结点，将这些结点删除后，如果其父结点只有1度，则一起删除
        for (int i = 0; i < n; ++i) {
            if (degrees[i] == 1 && coins[i] == 1) {
                //有金币的叶子节点，删除之
                degrees[i] = 0;
                Set<Integer> parents = nodeNeighbours[i];
                for (int parent : parents) {
                    //i被移除，i的parent度数-1
                    degrees[parent]--;
                    if (degrees[parent] == 1) {
                        //如果parent也是叶子节点，则一并删除
                        degrees[parent] = 0;
                    }
                }
            }
        }
        //最后扫一遍所有节点，剩余的需要移动的点数量为v
        int v = 0;
        for (int i = 0; i < n; ++i) {
            if (degrees[i] > 0) {
                v++;
            }
        }
        return Math.max(0, (v - 1) * 2);
    }

    public static void main(String[] args) {
        TopologicalSortSolution solution = new TopologicalSortSolution();
        Assert.isTrue(2 == solution.minimumFuelCost(Parser.parse("[[0,1],[1,2]]"), 3));
        Assert.isTrue(7 == solution.minimumFuelCost(Parser.parse("[[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]]"), 2));
        Assert.isTrue(4 == solution.minimumFuelCost(Parser.parse("[[0,1],[0,2],[1,3],[1,4]]"), 5));
        Assert.isTrue(3 == solution.minimumFuelCost(Parser.parse("[[0,1],[0,2],[0,3]]"), 5));
    }
}
